import collections
from typing import List


class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        count1 = collections.Counter()
        mx1, my1, mx2, my2 = float("inf"), float("inf"), float("-inf"), float("-inf")
        space = 0
        for x1, y1, x2, y2 in rectangles:
            count1[(x1, y1)] += 1
            count1[(x1, y2)] += 1
            count1[(x2, y1)] += 1
            count1[(x2, y2)] += 1
            space += (x2 - x1) * (y2 - y1)
            mx1, my1, mx2, my2 = min(mx1, x1), min(my1, y1), max(mx2, x2), max(my2, y2)
        count2 = collections.Counter(count1.values())
        return (count2[1] == 4
                and space == (mx2 - mx1) * (my2 - my1)
                and len(rectangles) == len(set(tuple(elem) for elem in rectangles))
                and count1[(mx1, my1)] == 1 and count1[(mx1, my2)] == 1
                and count1[(mx2, my1)] == 1 and count1[(mx2, my2)] == 1)


if __name__ == "__main__":
    # True
    print(Solution().isRectangleCover(rectangles=[
        [1, 1, 3, 3],
        [3, 1, 4, 2],
        [3, 2, 4, 4],
        [1, 3, 2, 4],
        [2, 3, 3, 4]
    ]))

    # False
    print(Solution().isRectangleCover(rectangles=[
        [1, 1, 2, 3],
        [1, 3, 2, 4],
        [3, 1, 4, 2],
        [3, 2, 4, 4]
    ]))

    # False
    print(Solution().isRectangleCover(rectangles=[
        [1, 1, 3, 3],
        [3, 1, 4, 2],
        [1, 3, 2, 4],
        [3, 2, 4, 4]
    ]))

    # False
    print(Solution().isRectangleCover(rectangles=[
        [1, 1, 3, 3],
        [3, 1, 4, 2],
        [1, 3, 2, 4],
        [2, 2, 4, 4]
    ]))

    # True
    print(Solution().isRectangleCover(
        rectangles=[[0, 0, 4, 1], [7, 0, 8, 2], [6, 2, 8, 3], [5, 1, 6, 3], [4, 0, 5, 1], [6, 0, 7, 2], [4, 2, 5, 3],
                    [2, 1, 4, 3], [0, 1, 2, 2], [0, 2, 2, 3], [4, 1, 5, 2], [5, 0, 6, 1]]))

    # 测试用例39 : False
    print(Solution().isRectangleCover([[0, 0, 1, 1], [0, 0, 2, 1], [1, 0, 2, 1], [0, 2, 2, 3]]))

    # 测试用例41 : False
    print(Solution().isRectangleCover([[0, 0, 3, 3], [1, 1, 2, 2], [1, 1, 2, 2]]))

    # 测试用例45 : False
    print(Solution().isRectangleCover(
        [[0, 0, 1, 1], [0, 2, 1, 3], [1, 1, 2, 2], [2, 0, 3, 1], [2, 2, 3, 3], [1, 0, 2, 3], [0, 1, 3, 2]]))
